W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Niniejsze zadanie to trudniejsza wersja zadania Rotacje na drzewie z II etapu XVIII OI. Nie wystąpiła ona w samym konkursie.
Ogrodnik Bajtazar zajął się hodowlą rzadkiego drzewa o nazwie Rotatus Informatikus. Ma ono bardzo ciekawe własności:
Bajtazar pochodzi ze starego miasta Bajtogrodu i jak wszyscy jego mieszkańcy bardzo lubi porządek. Zastanawia się, jak za pomocą rotacji jak najlepiej uporządkować swoje drzewo. Uporządkowanie drzewa mierzymy liczbą inwersji zawartych w jego koronie, tj. dla korony wyznaczamy liczbę takich par , , dla których .
Rys. 1. Oryginalne drzewo (po lewej) o koronie zawiera dwie inwersje.
Po rotacji otrzymujemy drzewo (po prawej) o koronie , które zawiera tylko jedną inwersję.
Każde z tych drzew ma 5 gałęzi.
Napisz program, który wyznaczy minimalną liczbę inwersji zawartych w koronie drzewa, które można otrzymać za pomocą rotacji wyjściowego drzewa Bajtazara.
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę liści drzewa Bajtazara. W kolejnych wierszach znajduje się opis drzewa. Drzewo definiujemy rekurencyjnie:
W jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą: minimalną liczbę inwersji w koronie drzewa, które można otrzymać za pomocą jakiegoś ciągu rotacji wyjściowego drzewa.
Dla danych wejściowych:
3 0 0 3 1 2
poprawną odpowiedzią jest:
1
Wyjaśnienie do przykładu: Rysunek 1 ilustruje drzewo z przykładu.
Autorzy zadania: Tomasz Kociumaka, Tomasz Waleń.